package com.fanshuai.algorithms.divide;

/**
 * 在给定数组中，返回第二小的数
 */
public class Last2Min {
    /**
     * 第二小的数
     * @param a
     * @return
     */
    public static int last2Min(int[] a) {
        int mid = (a.length - 1) / 2;

        int min1 = findMin(a, 0, mid);
        int min2 = findMin(a, mid + 1, a.length - 1);
        return Math.max(min1, min2);
    }

    private static int findMin(int[] a, int left, int right) {
        if (left == right) {
            return a[left];
        }

        int mid = (left + right) / 2;
        int minLeft = findMin(a, left, mid);
        int minRight = findMin(a,mid + 1, right);
        return Math.min(minLeft, minRight);
    }

    /**
     * 第三小的数  将a数组三等分，求最小值，然后取最大值
     * @param a
     * @return
     */
    public static int last3Min(int[] a) {
        int left = 0, right = a.length - 1;

        int m1 = left + (right - left) / 3;
        int m2 = left + (right - left) * 2 / 3;

        int min0 = findMin(a, 0, m1);
        int min1 = findMin(a, m1 + 1, m2);
        int min2 = findMin(a, m2 + 1, right);

        int min = Math.max(min0, min1);
        return Math.max(min, min2);
    }

    public static void main(String[] args) {
        int[] a = {-2, -1, -6, 11, -4, 13, -5, -3};

        System.out.println(last2Min(a));
        System.out.println(last3Min(a));
    }

}
